home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 076-100 / disk_085 / filereq / patmatch.c < prev    next >
C/C++ Source or Header  |  1992-05-06  |  6KB  |  275 lines
  1. /* PatMatch.c - Implements AmigaDos Regular Expression Pattern Matching.
  2. **
  3. **  This program will test whether a string is an AmigaDos  regular expression
  4. **  It may be used to implement wild expressions such as:
  5. **
  6. **    "copy #?.c to <dir>" to copy any file ending in .c
  7. **
  8. **  The program has two entry points: CmplPat, and Match.
  9. **
  10. **    CmplPat - takes a pattern and returns an auxilliary integer vector
  11. **              which is used by Match.  The pattern is not modified in
  12. **              any way.  CmplPat returns 1 if no errors were detected
  13. **              while compiling the pattern; otherwise it returns 0;
  14. **
  15. **    Match   - takes the pattern, the auxilliary vector, and the string
  16. **              to be matched.  It returns 1 if the string matches the
  17. **              pattern; otherwise it returns 0;
  18. **
  19. **  Translated from BCPL by:
  20. **              Jeff Lydiatt
  21. **              Richmond B.C. Canada
  22. **              16 May 1986.
  23. **
  24. **  Source: "A Compact Function for Regular Expression Pattern Matching",
  25. **           Software - Practice and Experience, September 1979.
  26. **
  27. **  Useage:
  28. **     To test if "file.c" matches the regular expression "#?.c"
  29. **     char *Pat = "#?.c";
  30. **     char *Str = "file.c";
  31. **     WORD Aux[128];
  32. **
  33. **     if ( CmplPat( Pat, Aux ) == 0 )
  34. **        {
  35. **           printf("Bad Wildcard Expression\n");
  36. **           exit(1);
  37. **        }
  38. **     if ( Match( Pat, Aux, Str ) == 1 )
  39. **        printf("String matches the pattern\n");
  40. **     else
  41. **        printf("String does NOT match the pattern\n");
  42. **/
  43.  
  44. /*--- Included files ----*/
  45.  
  46. #include <stdio.h>
  47. #include <exec/types.h>
  48. #include <ctype.h>
  49.  
  50. #define  EOS '\0'
  51.  
  52. /*--- Global Variables  ---*/
  53.  
  54. static char     Ch;      /* The current character in Pattern */
  55. static char     *Pat;    /* Pointer to the Pattern */
  56. static int      *Aux;    /* Pointer to returned auxilliary vector */
  57. static int      PatP;    /* Current position in Pat */
  58. static int      Patlen;  /* strlen(pat) */
  59. static BOOL     Errflag; /* TRUE if error */
  60. static int      *Work;   /* Pointer to Active work area */
  61. static int      Wp;      /* Current position in work */
  62. static BOOL     Succflag;/* True if "str" matches "pat" */
  63.  
  64. /*----------------------------------------------------------------*/
  65. /*                   The Interpreter                              */
  66. /*----------------------------------------------------------------*/
  67.  
  68. static void Put(N)
  69. int N;
  70. {
  71.    register int *ip;
  72.    register int *to;
  73.  
  74.    if ( N == 0 )
  75.       Succflag = TRUE;
  76.    else
  77.       {
  78.     for ( ip = &Work[ 1 ], to = &Work[ Wp ]; ip <= to; ip++)
  79.        if ( *ip == N )
  80.           return;
  81.     Work[ ++Wp ] = N;
  82.       }
  83. }
  84.  
  85. int Match( Pat, Aux, Str )
  86. char Pat[];
  87. int  Aux[];
  88. char Str[];
  89. {
  90.    int W[ 128 ];
  91.    int  S = 0;
  92.    int  I, N, Q, P, Strlength;
  93.    char K;
  94.    int  strlen();
  95.    void Put();
  96.  
  97.    Work = W;
  98.    Wp = 0;
  99.    Succflag = FALSE;
  100.    Strlength = strlen( Str );
  101.    Put( 1 );
  102.  
  103.    if ( Aux[ 0 ] != 0 )
  104.       Put( Aux[ 0 ] );
  105.  
  106.    for(;;)
  107.       {
  108.         /* First complete the closure */
  109.         for( N=1; N <= Wp; N++ )
  110.           {
  111.          P = Work[ N ];
  112.          K = Pat[ P-1 ];
  113.          Q = Aux[ P ];
  114.          switch( K )
  115.            {
  116.           case '#': Put( P + 1 );
  117.           case '%': Put( Q );
  118.           default : break;
  119.           case '(':
  120.           case '|': Put( P + 1);
  121.                 if ( Q != 0 )
  122.                    Put( Q );
  123.         }
  124.        }
  125.  
  126.     if ( S >= Strlength )
  127.        return Succflag;
  128.     if ( Wp == 0 )
  129.        return FALSE;
  130.     Ch = Str[ S++ ];
  131.  
  132.     /* Now deal with the match items */
  133.  
  134.     N = Wp;
  135.     Wp = 0;
  136.     Succflag = FALSE;
  137.  
  138.     for ( I = 1; I <= N; I++)
  139.       {
  140.          P = Work[ I ];
  141.          K = Pat[ P - 1 ];
  142.          switch( K )
  143.            {
  144.          case '#':
  145.          case '|':
  146.          case '%':
  147.          case '(': break;
  148.          case '\'': K = Pat[ P ];
  149.          default : if ( _toupper( Ch ) != _toupper( K ) )
  150.                   break;
  151.          case '?': /* Successful match */
  152.                 Put ( Aux[ P ] );
  153.         } /* End Switch */
  154.       } /* End For I */
  155.      } /* End for(;;) */
  156. }
  157.  
  158.  
  159. /*----------------------------------------------------------------*/
  160. /*                     The Compiler                               */
  161. /*----------------------------------------------------------------*/
  162.  
  163. static void  Rch() /* Read next character from Pat */
  164. {
  165.    if ( PatP >= Patlen )
  166.       Ch = EOS;
  167.    else
  168.       Ch = Pat[ PatP++ ];
  169. }
  170.  
  171. static void Nextitem() /* Get next char from Pat; recognize the ' escape char */
  172. {
  173.    if ( Ch == '\'' )
  174.       Rch();
  175.    Rch();
  176. }
  177.  
  178. static void Setexits( List, Val )
  179. int List;
  180. int Val;
  181. {
  182.    int A;
  183.  
  184.    do
  185.      {
  186.     A = Aux[ List ];
  187.     Aux[ List ] = Val;
  188.     List = A;
  189.      }
  190.     while ( List != 0 );
  191. }
  192.  
  193. static int Join( A, B )
  194. int A, B;
  195. {
  196.     int T = A;
  197.  
  198.     if ( A == 0 )
  199.     return B;
  200.     while ( Aux[ A ] != 0 )
  201.     A = Aux[ A ];
  202.     Aux[ A ] = B;
  203.     return T;
  204. }
  205.  
  206. static int Prim()      /* Parse a Prim symbol */
  207. {
  208.    int   A = PatP;
  209.    char Op = Ch;
  210.    int  Exp();
  211.    void Setexits(), Nextitem();
  212.  
  213.    Nextitem();
  214.    switch( Op )
  215.      {
  216.         case EOS:
  217.         case ')':
  218.         case '|': Errflag = TRUE;
  219.         default : return A;
  220.         case '#': Setexits( Prim(), A ); return A;
  221.         case '(': A = Exp( A );
  222.           if ( Ch != ')' )
  223.             {
  224.             Errflag = TRUE;
  225.             }
  226.           Nextitem();
  227.           return A;
  228.      }
  229. }
  230.  
  231. static int Exp( AltP )    /* Parse an expression */
  232. int AltP;
  233. {
  234.    int Exits = 0;
  235.    int A;
  236.    int Prim(), Exits(), Join();
  237.    void Nextitem(), Setexits();
  238.  
  239.    for (;;)
  240.     {
  241.        A = Prim();
  242.        if ( Ch == '|' || Ch == ')' || Ch == EOS )
  243.           {
  244.         Exits = Join( Exits, A );
  245.         if ( Ch != '|' )
  246.            return Exits;
  247.         Aux[ AltP ] = PatP;
  248.         AltP = PatP;
  249.         Nextitem();
  250.           }
  251.        else
  252.           Setexits( A, PatP );
  253.     }
  254. }
  255.  
  256. int CmplPat( Pattern, CmplPattern)
  257. char Pattern[];
  258. int  CmplPattern[];
  259. {
  260.    int i, strlen();
  261.    void Rch(), Setexits();
  262.  
  263.    Pat = Pattern;
  264.    Aux = CmplPattern;
  265.    PatP = 0;
  266.    Patlen = strlen( Pat );
  267.    Errflag = FALSE;
  268.  
  269.    for ( i = 0; i <= Patlen; i++ )
  270.       Aux[ i ] = 0;
  271.    Rch();
  272.    Setexits( Exp(0), 0 );
  273.    return (!Errflag);
  274. }
  275.